An optimal algorithm for finding all the jumps of a monotone step-function

The idea of binary search is generalized as follows. Given ?: {0, 1,…, N} → {0,…, K} such that $\text{?(0) = 0}$, $\text{?(N) = K}$, and $\text{?(i) ? ?(j)}$ for i < j, all the “jumps” of f, i.e., all is such that $\text{?(i) > ?(i ? 1)}$ together with the difference $\text{?(i) ? ?(i ? 1)}$ are recognized within f-evaluations. This is proved to be the exact bound in the non-trivial case when K ? N. An optimal strategy is as follows: The first query will be at i = 2^m, where $\text{m = [}\text{log}{}_2\text{(}\text{N}\text{K}\text{)]}$. An adversary will then respond either $\text{?(i) = 0}$ or $\text{?(i) - 1}$ as explained in the paper.     

Strategic behavior and social optimization in Markovian vacation queues: The case of heterogeneous customers

We consider a single server queueing system in which service shuts down when no customers are present, and is resumed when the queue length reaches a given critical length. We assume customers are heterogeneous on delay sensitivity and analyze customers’ strategic response to this mechanism and compare it to the overall optimal behavior. We provide algorithms to compute the equilibrium arrival rates and also derive the monotonicity of equilibrium and optimal arrival rates. We show that there may exist multiple equilibria in such a system and the optimal arrival rate may be larger or smaller than the decentralized equilibrium one.     

Rounding to an integral program

This paper presents a framework for approximating NP-hard problems that can be formulated as integer-covering programs, possibly with additional side constraints, and the number of covering options is restricted in some sense, although this property may be well hidden.     

Graph partitions with minimum degree constraints

Given a graph with n nodes and minimum degree δ, we give a polynomial time algorithm that constructs a partition of the nodes of the graph into two sets X and Y such that the sum of the minimum degrees in X and in Y is at least δ and the cardinalities of X and Y differ by at most δ(δ + 1 if n ≠ δ(mod2)). The existence of such a partition was shown by Sheehan (1988).     

Weber blockade theory of magnetoresistance oscillations in superconducting strips

Recent experiments on the conductance of thin, narrow superconducting strips have found periodic fluctuations, as a function of the perpendicular magnetic field, with a period corresponding to approximately two flux quanta per strip area [A. Johansson et al., Phys. Rev. Lett. 95, 116805 (2005)]. We argue that the low-energy degrees of freedom responsible for dissipation correspond to vortex motion. Using vortex-charge duality, we show that the superconducting strip behaves as the dual of a quantum dot, with the vortices, magnetic field, and bias current respectively playing the roles of the electrons, gate voltage, and source-drain voltage. In the bias-current versus magnetic-field plane, the strip conductance displays regions of small vortex conductance (i.e., small electrical resistance) that we term "Weber blockade" diamonds, which are dual to Coulomb blockade diamonds in quantum dots.     

Helical liquids and Majorana bound states in quantum wires

We show that the combination of spin-orbit coupling with a Zeeman field or strong interactions may lead to the formation of a helical electron liquid in single-channel quantum wires, with spin and velocity perfectly correlated. We argue that zero-energy Majorana bound states are formed in various situations when such wires are situated in proximity to a conventional s-wave superconductor. This occurs when the external magnetic field, the superconducting gap, or, most simply, the chemical potential vary along the wire. These Majorana states do not require the presence of a vortex in the system. Experimental consequences of the helical liquid and the Majorana states are also discussed.     

Flow trees for vertex-capacitated networks

Given a graph G=(V,E) with a cost function , we want to represent all possible min-cut values between pairs of vertices i and j. We consider also the special case with an additive cost c where there are vertex capacities c(v)?0∀v∈V, and for a subset S⊆V, c(S)=∑_v∈Sc(v). We consider two variants of cuts: in the first one, separation, {i} and {j} are feasible cuts that disconnect i and j. In the second variant, vertex-cut, a cut-set that disconnects i from j does not include i or j. We consider both variants for undirected and directed graphs. We prove that there is a flow-tree for separations in undirected graphs. We also show that a compact representation does not exist for vertex-cuts in undirected graphs, even with additive costs. For directed graphs, a compact representation of the cut-values does not exist even with additive costs, for neither the separation nor the vertex-cut cases.     

Amplitude-dependent frequency, desynchronization, and stabilization in noisy metapopulation dynamics

The enigmatic stability of population oscillations within ecological systems is analyzed. The underlying mechanism is presented in the framework of two interacting species free to migrate between two spatial patches. It is shown that the combined effects of migration and noise cannot account for the stabilization. The missing ingredient is the dependence of the oscillations' frequency upon their amplitude. A simple model of diffusively coupled oscillators allows the derivation of quantitative results, like the functional dependence of the desynchronization upon diffusion strength and frequency differences. The oscillations' amplitude is shown to be (almost) noise independent.     

z-Approximations

Approximation algorithms for NP-hard optimization problems have been widely studied for over three decades. Most of these measure the quality of the solution produced by taking the ratio of the cost of the solution produced by the algorithm to the cost of an optimal solution. In certain cases, this ratio may not be very meaningful—for example, if the ratio of the worst solution to the best solution is at most some constant α, then an approximation algorithm with factor α may in fact yield the worst solution! To overcome this hurdle (among others), several authors have independently suggested the use of a different measure which we call z-approximation. An algorithm is an α z-approximation if it runs in polynomial time and produces a solution whose distance from the optimal one is at most α times the distance between the optimal solution and the worst possible solution. The results known so far about z-approximations are either of the inapproximability type or rather straightforward observations. We design polynomial time algorithms for several fundamental discrete optimization problems; in particular we obtain a z-approximation factor of for the

Full-size image

(TSP) (with no triangle inequality assumption). For the TSP this improves to . We also show that if there is a polynomial time algorithm that for any fixed ε > 0 yields an ε z-approximation then P = NP. We also present z-approximations for severa1 other problems such as

Full-size image

, and

Full-size image

.